package com.garfield.tree;

import java.awt.*;
import java.util.PrimitiveIterator;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        //创建一棵二叉树
        BinaryTree tree = new BinaryTree();
        //创建需要的节点
        HeroNode root = new HeroNode(1,"宋江");
        HeroNode heroNode2 = new HeroNode(2,"吴用");
        HeroNode heroNode3 = new HeroNode(3,"卢俊义");
        HeroNode heroNode4 = new HeroNode(4,"林冲");
        HeroNode heroNode5 = new HeroNode(5,"关胜");

        //手动创建二叉树
        root.setLeft(heroNode2);
        root.setRight(heroNode3);
        heroNode3.setRight(heroNode4);
        heroNode3.setLeft(heroNode5);
        tree.setRoot(root);

        System.out.println("前序遍历：");//预测应该输出顺序为12354
        tree.preOrder();

        System.out.println("中序遍历：");//预测应该输出顺序为21534
        tree.infixOrder();

        System.out.println("后序遍历：");//预测应该输出顺序为25431
        tree.postOrder();

        System.out.println("前序遍历方式查找：");
        HeroNode res1 = tree.preOrderSearch(5);
        System.out.println(res1);

        System.out.println("中序遍历方式查找：");
        HeroNode res2 = tree.infixOrderSearch(5);
        System.out.println(res2);


        System.out.println("后序遍历方式查找：");
        HeroNode res3 = tree.postOrderSearch(5);
        System.out.println(res3);
    }
}

//定义一个BinaryTree
class BinaryTree{
    private HeroNode root;

    public void setRoot(HeroNode root){
        this.root = root;
    }

    //前序遍历
    public void preOrder(){
        if(this.root != null){
            this.root.preOrder();//preOrder()里的this指向root
        }else {
            System.out.println("二叉树为空，无法遍历！");
        }
    }

    //中序遍历
    public void infixOrder(){
        if(this.root != null){
            this.root.infixOrder();
        }else {
            System.out.println("二叉树为空，无法遍历！");
        }
    }

    //后序遍历
    public void postOrder(){
        if(this.root != null){
            this.root.postOrder();
        }else {
            System.out.println("二叉树为空，无法遍历！");
        }
    }

    //前序遍历查找
    public HeroNode preOrderSearch(int no){
        HeroNode res = new HeroNode(0,"");
        if(root != null){
            res = this.root.preOrderSearch(no);
        }else {
            return null;
        }
        return res;
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no){
        HeroNode res = new HeroNode(0,"");
        if(root != null){
            res = this.root.infixOrderSearch(no);
        }else{
            return null;
        }
        return res;
    }

    //后序遍历查找
    public HeroNode postOrderSearch(int no){
        HeroNode res = new HeroNode(0,"");
        if(root != null){
            res = this.root.postOrderSearch(no);
        }else{
            return null;
        }
        return res;
    }
}

//创建HeroNode节点
class HeroNode{
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;
    public HeroNode(int no, String name){
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历的方法
    public void preOrder(){
        System.out.println(this);//先输出父节点
        //左子树
        if(this.left != null){
            this.left.preOrder();
        }
        //右子树
        if(this.right != null){
            this.right.preOrder();
        }
    }

    //中序遍历的方法
    public void infixOrder(){
        //左子树
        if(this.left != null){
            this.left.infixOrder();
        }
        System.out.println(this);//输出父节点
        //右子树
        if(this.right != null){
            this.right.infixOrder();
        }
    }

    //后序遍历的方法
    public void postOrder(){
        //左子树
        if(this.left != null){
            this.left.postOrder();
        }
        //右子树
        if(this.right != null){
            this.right.postOrder();
        }
        System.out.println(this);//输出父节点
    }

    //一定要注意进入if的次数和实际比较的次数是有差异的，进入了if可能只是进入了子树，但并没有比较是否匹配。println应该写在真正的比较语句(this.no == no)前输出，才能统计真正的比较次数。
    
    //前序遍历查找
    //根据编号no查找节点
    public HeroNode preOrderSearch(int no){
        System.out.println("统计前序遍历的比较次数");
        //父节点
        if(this.no == no){
            return this;
        }
        HeroNode res = null;//返回的答案
        //遍历左节点
        if(this.left != null){
            res = this.left.preOrderSearch(no);
        }
        //在左边找到了，可以直接返回，不需要再遍历右边
        if(res != null){
            return res;
        }
        //遍历右节点
        if(this.right != null){
            res = this.right.preOrderSearch(no);
        }
        //右节点遍历完后，不论是否为空，都要返回
        return res;
    }

    //中序遍历查找
    public HeroNode infixOrderSearch(int no){
        if(this == null){
            return null;
        }
        HeroNode res = null;//返回的答案
        //遍历左节点
        if(this.left != null){
            res = this.left.infixOrderSearch(no);
        }
        //在左边找到了，可以直接返回，不需要再遍历父节点
        if(res != null){
            return res;
        }
        System.out.println("统计中序遍历的比较次数");
        //父节点
        if(this.no == no){
            return this;
        }
        //遍历右节点
        if(this.right != null){
            res = this.right.infixOrderSearch(no);
        }
        //右节点遍历完后，不论是否为空，都要返回
        return res;
    }

    //后序遍历查找
    public HeroNode postOrderSearch(int no){
        if(this == null){
            return null;
        }
        HeroNode res = null;//返回的答案
        //遍历左节点
        if(this.left != null){
            res = this.left.postOrderSearch(no);
        }
        //在左边找到了，可以直接返回，不需要再遍历父节点
        if(res != null){
            return res;
        }
        //遍历右节点
        if(this.right != null){
            res = this.right.postOrderSearch(no);
        }
        if(res != null){
            return res;
        }
        System.out.println("统计后序遍历的比较次数");
        //父节点
        if(this.no == no){
            return this;
        }
        return null;
    }
}
